貌似 @DDF_Van 大佬的标程过不了 , 有些题解用的二分会多一个,那就补一发倍增题解吧。
Solution 1
设表示走了不多于条边,的最大边权(走不通为极小值)
如果有的一条边,那么(为这条边的权值)
那么转移为:
显然,如果存在 , 那么答案为。
时间复杂度 , 70分。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 300;
int n , m , x , y , z , w , Ans;
int dp[ MAXN + 5 ][ MAXN + 5 ][ MAXN + 5 ];
int main( ) {
memset( dp , 0xcf , sizeof( dp ) );
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d %d %d",&x,&y,&z,&w);
dp[ 1 ][ x ][ y ] = z;
dp[ 1 ][ y ][ x ] = w;
}
for( int s = 2 ; s <= n ; s ++ ) {
for( int k = 1 ; k <= n ; k ++ )
for( int i = 1 ; i <= n ; i ++ ) {
for( int j = 1 ; j <= n ; j ++ )
dp[ s ][ i ][ j ] = max( dp[ s ][ i ][ j ] , dp[ s - 1 ][ i ][ k ] + dp[ 1 ][ k ][ j ] );
if( dp[ s ][ i ][ i ] > 0 ) {
Ans = s;
goto there;
}
}
}
there:;
printf("%d",Ans);
return 0;
}
Solution 2
我们有必要重新定义一下转移式,设表示走了不超过条边,的最大边权(走不通为极小值)。
那么转移为:
我们可以用预处理求出。
在我们计算答案时,我们用类似倍增爬树的方法。
先尝试走了不超过条边从走到了的最小边权和 , 从大到小枚举。
1.如果没有正环,说明答案大于 , 那么下一步增加条边
转移时需用到上一次状态,用记录上一次尝试的最长路径。
2.如果有正环,说明答案小于等于,那么下一步尝试条边
倍增时间复杂度为 , 总时间复杂度。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 300 , MAXK = 10;
int n , m , x , y , z , w , Ans;
int dp[ MAXK + 5 ][ MAXN + 5 ][ MAXN + 5 ];
int tmp[ MAXN + 5 ][ MAXN + 5 ] , now[ MAXN + 5 ][ MAXN + 5 ];
int main( ) {
memset( now , 0xcf , sizeof( now ) );
memset( dp , 0xcf , sizeof( dp ) );
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d %d %d",&x,&y,&z,&w);
dp[ 0 ][ x ][ y ] = z;
dp[ 0 ][ y ][ x ] = w;
}
for( int i = 1 ; i <= n ; i ++ )
now[ i ][ i ] = 0 , dp[ 0 ][ i ][ i ] = 0;
for( int s = 1 ; s <= MAXK ; s ++ ) //预处理
for( int k = 1 ; k <= n ; k ++ )
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
dp[ s ][ i ][ j ] = max( dp[ s ][ i ][ j ] , dp[ s - 1 ][ i ][ k ] + dp[ s - 1 ][ k ][ j ] );
for( int s = MAXK ; s >= 0 ; s -- ) {
memset( tmp , 0xcf , sizeof( tmp ) );
for( int k = 1 ; k <= n ; k ++ ) //转移
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
tmp[ i ][ j ] = max( tmp[ i ][ j ] , now[ i ][ k ] + dp[ s ][ k ][ j ] );
bool f = 0;
for( int i = 1 ; i <= n ; i ++ )
if( tmp[ i ][ i ] > 0 ) {
f = 1;
break;
}
if( f ) continue; //有正环
else { //无正环
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
now[ i ][ j ] = tmp[ i ][ j ];
Ans += 1 << s;
}
}
printf("%d\n", Ans >= n ? 0 : Ans + 1 );
return 0;
}